0690. 员工的重要性【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

你有一个保存员工信息的数据结构，它包含了员工唯一的 id，重要度和直系下属的 id。

给定一个员工数组 employees，其中：

• employees[i].id 是第 i 个员工的 ID。
• employees[i].importance 是第 i 个员工的重要度。
• employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。

给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。

---

示例 1：

输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
输出：11
解释：
员工 1 自身的重要度是 5，他有两个直系下属 2 和 3，而且 2 和 3 的重要度均为 3。因此员工 1 的总重要度是 5 + 3 + 3 = 11。

示例 2：

输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5
输出：-3
解释：员工 5 的重要度为 -3 并且没有直接下属。
因此，员工 5 的总重要度为 -3。

---

提示：

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• 所有的 employees[i].id 互不相同。
• -100 <= employees[i].importance <= 100
• 一名员工最多有一名直接领导，并可能有多名下属。
• employees[i].subordinates 中的 ID 都有效。

2. 🎯 s.1 - DFS

c

// LeetCode C 提供的 Employee 结构不同，这里提供标准实现
int getImportanceHelper(int** graph, int* importance, int* subCount, int id, int n) {
    int total = importance[id];
    for (int i = 0; i < subCount[id]; i++)
        total += getImportanceHelper(graph, importance, subCount, graph[id][i], n);
    return total;
}

js

/**
 * @param {Employee[]} employees
 * @param {number} id
 * @return {number}
 */
var GetImportance = function (employees, id) {
  const map = new Map()
  for (const e of employees) map.set(e.id, e)
  const dfs = (eid) => {
    const e = map.get(eid)
    let total = e.importance
    for (const sub of e.subordinates) total += dfs(sub)
    return total
  }
  return dfs(id)
}

py

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        mp = {e.id: e for e in employees}
        def dfs(eid):
            e = mp[eid]
            return e.importance + sum(dfs(sub) for sub in e.subordinates)
        return dfs(id)

• 时间复杂度：$O(n)$，其中 n 是员工数量
• 空间复杂度：$O(n)$

算法思路：

• 建立 id 到员工的哈希映射
• 从目标员工开始DFS，累加自身 importance 和所有下属的递归结果